package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;
public class Nc42 {
    public class Solution {
        public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
            dfs(0, num);
            return res;
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        public void dfs(int idx, int[] nums) {
            //尝试拿当前位置去和后面的元素做交换，利用set记录以及交换过的值
            if (idx == nums.length) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = 0; i < nums.length; i++) {
                    list.add(nums[i]);
                }
                res.add(list);
                return;
            }
            Set<Integer> set = new HashSet<>();
            for (int i = idx + 1; i < nums.length; i++) {
                if (nums[i] != nums[idx] && !set.contains(nums[i])) {
                    swap(i, idx, nums);

                    dfs(idx + 1, nums);
                    //避免分支污染
                    swap(i, idx, nums);
                    set.add(nums[i]);
                }
            }
            dfs(idx + 1, nums);
        }
        
        public void swap(int i, int j, int[] nums) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

    @Test 
    public void test() {
        Solution s = new Solution();
        int[] num = {1,1,2};
        ArrayList<ArrayList<Integer>> res = s.permuteUnique(num);
        System.out.println(res);
        
    }
}
